package cn.cxq.learning.sort;

import java.util.Arrays;

/**
 * 希尔排序，简单来说就是分组从离散（多）到密集（少）的一个排序过程，为的是避免插入排序中的过多的数据交换。
 */
public class ShellSort {

    /**
     *使用交换法（交换实现插入，因为模拟出来的感觉也是一个有序数组的不断增长）来实现希尔排序
     * @param arr
     * @return
     */
    public static int[] printSort(int[] arr){

        //确定步长
        for (int step = arr.length/2; step > 0; step /= 2){
            for (int i = step; i < arr.length; i++) {
                for (int j = i - step; j >= 0; j -= step) {
                    if (arr[j] > arr[j + step]){
                        int temp = arr[j];
                        arr[j] = arr[j + step];
                        arr[j + step] = temp;
                    }
                }
            }
            System.out.println(Arrays.toString(arr));
        }
        return arr;
    }

    public static int[] sort(int[] arr){

        //确定步长
        for (int step = arr.length/2; step > 0; step /= 2){
            for (int i = step; i < arr.length; i++) {
                for (int j = i - step; j >= 0; j -= step) {
                    if (arr[j] > arr[j + step]){
                        int temp = arr[j];
                        arr[j] = arr[j + step];
                        arr[j + step] = temp;
                    }
                }
            }
        }
        return arr;
    }

    public static int[] printSort2(int[] arr){

        //确定步长
        for (int step = arr.length/2; step > 0; step /= 2){
            //这中间的这些和插入排序写的结构一样。
            for (int i = step; i < arr.length; i++) {
                int insert = arr[i];
                for (int j = i - step; j >= 0 ; j -= step) {
                    if (arr[j] > arr[j + step]){
                        arr[j + step] =arr[j];
                    }else {
                        arr[j + step] = insert;
                        break;
                    }
                }
            }
            System.out.println(Arrays.toString(arr));
        }
        return arr;
    }

    public static int[] sort2(int[] arr){

        //确定步长
        for (int step = arr.length/2; step > 0; step /= 2){
            //这中间的这些和插入排序写的结构一样。
            for (int i = step; i < arr.length; i++) {
                int insert = arr[i];
                for (int j = i - step; j >= 0 ; j -= step) {
                    if (arr[j] > arr[j + step]){
                        arr[j + step] =arr[j];
                    }else {
                        arr[j + step] = insert;
                        break;
                    }
                }
            }
        }
        return arr;
    }
}
